#include <iostream>     // std::cout, std::cin
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <stack>       // std::stack

#include "Ej3.h"
#include "UnionFind.h"

using namespace std;

Arista::Arista(int _nodoU,int _nodoV,int _costo):nodoU(_nodoU),nodoV(_nodoV),costo(_costo){}
Arista::Arista(){}
Solucion::Solucion(vector<Arista> _aristasAnillo, vector<Arista> _arstasRestantes, unsigned int _costoMinimo):aristasAnillo(_aristasAnillo), aristasRestantes(_arstasRestantes), costoMinimo(_costoMinimo){}
//~ Solucion::Solucion(stack<unsigned int> _aristasAnillo, vector<Arista> _arstasRestantes, unsigned int _costoMinimo):aristasAnillo(_aristasAnillo), aristasRestantes(_arstasRestantes), costoMinimo(_costoMinimo){}
Solucion::Solucion(){};

pair<vector<Arista>,unsigned int> recibir_entradas()
{
  int equipo1,equipo2, costoEnlace;
  unsigned int n,m;
  cin >> n;			//cantidad de equipos
  cin >> m;			//cantidad de enlaces
  
  vector<Arista> aristas;
  
  for(unsigned int i = 0; i < m; i++)
  {
	 cin >> equipo1;
	 cin >> equipo2;
	 cin >> costoEnlace;	 
	
	 aristas.push_back(Arista(equipo1,equipo2,costoEnlace));	 
  }  

 return make_pair(aristas,n);
}

bool comparacionArista (Arista i, Arista j)
{
	return (i.costo > j.costo);
}

//DFS
vector<Arista> encontrarCiclo(vector< vector<unsigned int> > grafo, unsigned int nodoInicial,unsigned int nodoFinal){
	vector<Arista> ciclo;
	vector<bool> nodoVisitado(false,grafo.size());
	unsigned int nodo = nodoInicial;
	stack<unsigned int> pila;	
	vector<unsigned int> pred(grafo.size(),0);
	
	pred[nodo] = 0;	
	pila.push(nodo);	
	while(!pila.empty()){
		
		nodo = pila.top();
		pila.pop();		
		nodoVisitado[nodo] = true;
		for(vector<unsigned int>::iterator hijo = grafo[nodo].begin();hijo!=grafo[nodo].end();hijo++){			
			if(!nodoVisitado[*hijo]){
				pred[*hijo] = nodo;
				pila.push(*hijo);
			}
		}		
	}
	ciclo.push_back(Arista(nodoInicial,nodoFinal,0));	
	nodo = nodoFinal;	
	while(pred[nodo] != 0){			
			ciclo.push_back(Arista(nodo,pred[nodo],0));
			nodo = pred[nodo];
		
	}	
	return ciclo;
}


Solucion kruscal(){
	unsigned int cantAristasEnArbol,cantNodos,costoTotal;
	bool encontreAnillo = false;
	vector<Arista> aristasDelAnillo;
	vector<Arista> aristasArbol;
	
	pair<vector<Arista>,unsigned int> entrada = recibir_entradas();
	
	vector<Arista> aristas = entrada.first;
	cantNodos = entrada.second;

	vector< vector<unsigned int> > grafo(cantNodos+1);
	
	//Esta estructura se usará para quitar de la estructura principal las aristas que estén en el ciclo(O(n²))
	bool aristasAnillo[cantNodos+1][cantNodos+1];	
	for(unsigned int i =0; i<=cantNodos;i++)
		for(unsigned int j =0; j<=cantNodos;j++)
				aristasAnillo[i][j] = false;
	//O(n log(n))
	sort(aristas.begin(),aristas.end(),comparacionArista);
	
	UnionFind grupos(cantNodos);
	
	cantAristasEnArbol = 0;
	costoTotal = 0;
	Arista arista;
	while(cantAristasEnArbol <= cantNodos-1 && !aristas.empty() ){
		arista = aristas.back();
		aristas.pop_back();
		
		if(!grupos.find(arista.nodoU,arista.nodoV)){
			//Guardo las aristas del AGM
			aristasArbol.push_back(arista);
			
			costoTotal += arista.costo;
			grupos.unioN(arista.nodoU,arista.nodoV);
			
			//Construyo AGM
			grafo[arista.nodoU].push_back(arista.nodoV);
			grafo[arista.nodoV].push_back(arista.nodoU);
			
			cantAristasEnArbol++;
			
		}else if(!encontreAnillo){
			//La primer arista que forme un ciclo pertenecerá a la solución ya que tiene peso minimo	
			encontreAnillo = true;
			
			costoTotal += arista.costo;			
			//Hago DFS para recorrer el árbol y encontrar un camino entre los extremos de la arista que forma el ciclo
			aristasDelAnillo = encontrarCiclo(grafo, arista.nodoU,arista.nodoV);
			
			//Marco en la matriz las aristas que pertenecen al  ciclo
			for(vector<Arista>::iterator pos = aristasDelAnillo.begin();pos != aristasDelAnillo.end();pos++){				
				aristasAnillo[pos->nodoU][pos->nodoV] = true;
				aristasAnillo[pos->nodoV][pos->nodoU] = true;
			}
			
			for(vector<Arista>::iterator pos = aristasArbol.begin();pos != aristasArbol.end();pos++){
				//Las aristas que estan en el ciclo no tienen que estar en el resto de la estructura
				if(aristasAnillo[pos->nodoU][pos->nodoV]){
					//Al borrar se modifica el iterador siendo pos el siguiente elemento, por ende tenemos que modificarlo para que el bucle
					//no saltee elementos
					pos=aristasArbol.erase(pos);
					pos--;
				}
			}			

		}		
		
	}	
	
	if(cantAristasEnArbol != cantNodos-1 || !encontreAnillo )
		return Solucion();
	
	return Solucion(aristasDelAnillo,aristasArbol,costoTotal);
}


int main()
{
	Solucion sol;
	sol = kruscal();
	if(!sol.aristasRestantes.empty() && !sol.aristasAnillo.empty() ){
		//Imprimo primer línea de la solución
		cout << sol.costoMinimo << " " << sol.aristasAnillo.size() << " " << sol.aristasRestantes.size() << endl;	
		//Imprimpo aristas en el ciclo
		for(vector<Arista>::iterator pos = sol.aristasAnillo.begin();pos != sol.aristasAnillo.end();pos++){
			cout <<pos->nodoU<<" "<<pos->nodoV<<endl;
		}
		//Imprimo aristas en el resto de la estructura
		for(vector<Arista>::iterator pos = sol.aristasRestantes.begin();pos != sol.aristasRestantes.end();pos++){
			cout <<pos->nodoU<<" "<<pos->nodoV<<endl;
		}	
	}else
		cout << "no" << endl;
  
  return 0;
}
